With the evolution of the information society, services using an information network, such as an electronic payment network or a basic resident register network, have been in widespread use. To operate such services safely, information security technology has been used. The following two types of encryption method have been developed as encryption methods used as fundamental technology for information security: a public key cryptosystem and a common key cryptosystem. In the common key cryptosystem, the same private key is used for encryption and decryption. By using the private key as information that is secret from any third party other than the users, the security is ensured in the common key cryptosystem. In the public key cryptosystem, a public key that is used for encryption is made available to the public. In contrast, the private key used for decryption is used as information that is secret from any third party other than the users. In this manner, the security is ensured.
In both the public key cryptosystem and the common key cryptosystem, the security of the cryptosystem depends on security of the private key. If the private key is known to a third party, security of the cryptosystem is not ensured. To decrease the probability of a third party knowing the private key, a method for generating a private key using a random number has been developed.
Random numbers fall into the following two categories: a pseudo random number and a physical random number. A pseudo random number is a sequence of numbers generated through deterministic calculation. By performing calculation on an initial value (also referred to as a “seed”) according to a predetermined algorithm, a pseudo random number is generated. A pseudo random number is easily cracked by an attacker if the pseudo random number algorithm and the initial value are available to the attacker. Accordingly, if a pseudo random number is used, there is a risk of the attacker guessing the private key. In contrast, a physical random number is generated using a random physical phenomenon, such as thermal noise output from an element that constitutes an electronic circuit. A physical random number is not reliable and, thus, is unpredictable. By generating a private key using a physical random number, security of the physical random number is increased. In addition, a physical random number generator using a meta table of an electronic circuit has been developed. The physical random number generator using a meta table of an electronic circuit is able to generate a physical random number that is hard to predict without a large circuit scale configuration.
In addition, end users of a service, such as the electronic payment network or the basic resident register network, may use a smart card. The smart card incorporates an IC chip, which stores a private key in a memory region of the IC chip. The IC chip incorporated into the smart card performs an encryption process, decryption process, a digital signature process, and a digital authentication process. When these processes are performed, a private key is used. The hardware resources of a compact device, such as smart card, are limited. In addition, electric power available for the compact device is limited. Accordingly, it is desirable that the compact devices have a random number generator that use much less power.
A random number generating method including a process for operating a flip-flop under a metastable condition and a process for generating a random bit based on the metastable condition has been developed. In addition, a random number generating circuit including a counter circuit that receives a clock signal and a random signal and outputs a count value of the clock signal in accordance with varying random signal and a latch circuit that latches the count value with varying random signal and outputs a random number signal has been developed.
Furthermore, a random number generator including a plurality of random number output circuits, an exclusive OR circuit, a random number determination circuit, and a random number generation instruction inhibiting unit has been developed. The exclusive OR circuit of the random number generator obtains an exclusive OR of the outputs of the plurality of random number output circuits. The random number determination circuit of the random number generator determines whether the output of each of the random number output circuits generated in response to a random number generation instruction is a random number. In addition, the random number generation instruction inhibiting unit of the random number generator inhibits a random number generation instruction from being sent to any one of the random number output circuits having the output determined not to be a random number by the random number determination circuit.
FIG. 1 is a circuit block diagram illustrating an example of an RS latch circuit used as a random number output circuit of a random number generator.
An RS latch circuit 10 includes a first NAND element 101, a second NAND element 102, an input terminal 103, and an output terminal 104. A first input terminal (0) of the first NAND element 101 and a second input terminal (1) of the second NAND element 102 are connected to the input terminal 103. A second input terminal (1) of the first NAND element 101 is connected to an output terminal of the second NAND element 102. A first input terminal (0) of the second NAND element 102 is connected to an output terminal of the first NAND element 101 and the output terminal 104.
When a signal of an L (Low) level is input to the input terminal 103 of the RS latch circuit 10, a signal output from the output terminal 104 has stably an H (High) level. If the signal input to the input terminal 103 of the RS latch circuit 10 is changed from the L level to an H level, the output signal of the first NAND element 101 and the output signal of the second NAND element 102 interfere with each other and, thus, the RS latch circuit 10 enters a “metastable state” in which the RS latch circuit 10 is unstable. After the RS latch circuit 10 enters a metastable state, the signal of the output terminal 104 becomes stable at either an L level or an H level. If the delay time of the first NAND element 101 is substantially the same as the delay time of the second NAND element 102, the probability of the signal output from the output terminal 104 having an L level is substantially the same as the probability of the signal output from the output terminal 104 having an H level. However, the driving capabilities and the widths of interconnection lines for connecting the terminals, for example, of the first NAND element 101 and the second NAND element 102 differ from each other. Accordingly, the signal level of the output terminal 104 after the RS latch circuit 10 enters a metastable state varies from RS latch circuit to RS latch circuit. For example, if the driving capabilities of the first NAND element 101 and the second NAND element 102 differ from each other, the signal of the output terminal 104 after the RS latch circuit 10 enters a metastable state is highly likely to be continuously output at either the L level or the H level. Alternatively, if the driving capabilities and the widths of interconnection lines for connecting the terminals of the first NAND element 101 and the second NAND element 102 are substantially the same, the signal level of the output terminal 104 after the RS latch circuit 10 enters a metastable state is uncertain.
When a clock signal alternately having an L level and an H level at predetermined intervals is input to the input terminal 103 of the RS latch circuit 10, the RS latch circuit 10 is classified into one of the following three types according to the output. That is, an RS latch circuit 10 of a first type changes the signal level of the output terminal 104 to either an L level or an H level in accordance with a rising edge of the clock signal. After entering a metastable state, the RS latch circuit 10 of a first type outputs a bit string including random L levels and H levels, that is, a random number. An RS latch circuit 10 of a second type maintains the signal level of the output terminal 104 at an L level after entering a metastable state. An RS latch circuit 10 of a third type maintains the signal level of the output terminal 104 at an H level after entering a metastable state. Since the RS latch circuits 10 of the second type and the third type continue to output signals of an H level and an L level, respectively, while the clock signal of an H level is being input, the RS latch circuits 10 do not function as random number output circuits. Hereinafter, if the signal level of the output terminal 104 of the RS latch circuit 10 becomes a fixed signal level (an L level or an H level) after the RS latch circuit 10 enters a metastable state, the following expression is used: “the RS latch circuit 10 outputs a fixed number.” In addition, if the signal level of the output terminal 104 of the RS latch circuit 10 is capable of being either the L level or the H level after the RS latch circuit 10 enters a metastable state, the following expression is used: “the RS latch circuit 10 outputs a random number.”
In addition, to avoid a clone product having the same or substantially the same features and functionality as a genuine product, an authentication feature may be added to a genuine product. To achieve the authentication feature to be added to a genuine product, a physically unclonable Function (PUF) has been developed. A latch PUF, which is one type of PUF, employs a circuit having the same configuration as the RS latch circuit 10 illustrated in FIG. 1 as a basic circuit configuration.
FIG. 2 is a circuit block diagram of the latch PUF.
A latch PUF 200 includes a plurality of RS latch circuits 10-1 to 10-N, each of which is the RS latch circuit 10 illustrated in FIG. 1. After a signal of an H level is input to the input terminal 103 and, thus, the latch PUF 200 enters a metastable state, the latch PUF 200 uses a fixed number output signal of an L level or an H level output from the output terminal 104 of the RS latch circuit 10 as individual-specific information. The reference numbers 103 and 104 are not illustrated in FIGS. 2 and 3. As an example, an individual-specific information generating unit (not illustrated) generates the individual-specific information by arranging the outputs of the RS latch circuits 10 each having a fixed output value based on the order information defined for each of the RS latch circuits 10.
In the example illustrated in FIG. 2, the RS latch circuits 10-1 and 10-N continue to output a signal of an L level after entering a metastable state throughout a predetermined clock period. Accordingly, the RS latch circuits 10-1 and 10-N are used as an individual-specific information generating circuit that generates a signal of an L level. In addition, the RS latch circuit 10-2 continues to output a signal of an H level after entering a metastable state throughout a predetermined clock period. Accordingly, the RS latch circuit 10-2 is used as an individual-specific information generating circuit that generates a signal of an H level. In contrast, each of the RS latch circuits 10-3 and 10-(N−1) outputs a signal of an L level and a signal of an H level (that is, a random number) throughout a predetermined clock period. If the RS latch circuits 10-3 and 10-(N−1) that output a random number are used as an individual-specific information generating circuit, the individual-specific information that is determined to be unique for each device varies. As a result, the reliability of the individual-specific information is lost. Since the reliability of the individual-specific information generated by the latch PUF 200 is lost, it is not desirable that the RS latch circuits 10-3 and 10-(N−1) be used as an individual-specific information generating circuit.
In addition, a latch PUF that uses an RS latch circuit that outputs a fixed number and an RS latch circuit that outputs a random number has been developed.
FIG. 3 is a circuit block diagram of a latch PUF that uses an RS latch circuit that outputs a fixed number and an RS latch circuit that outputs a random number.
A latch PUF 300 includes RS latch circuits 10-1 to 10-6, each of which is the RS latch circuit 10 illustrated in FIG. 1, and a determination circuits 301-1 to 301-6, each of which is a determination circuit 301. The determination circuits 301-1 to 301-6 determine the types of the output signals of RS latch circuits 10-1 to 10-6, respectively. Input terminals 103 of the RS latch circuits 10-1 to 10-6 receive clock signals having the same cycle. When the clock signal is input, the determination circuit 301 monitors the output signal throughout a predetermined clock period after the RS latch circuit 10 enters a metastable state. If the signal level of the output signal of the RS latch circuit 10 after the RS latch circuit 10 enters a metastable state is an L level throughout the monitored predetermined clock period, the determination circuit 301 outputs two signals of an L level, that is, “00”. In contrast, if the signal level of the output signal of the RS latch circuit 10 after the RS latch circuit 10 enters a metastable state is an H level throughout the monitored predetermined clock period, the determination circuit 301 outputs two signals of an H level, that is, “11”. When a random number is generated during the monitored predetermined clock period and if there are many signals of an L level in the generated random number, the determination circuit 301 outputs a signal of an L level and a signal of an H level, that is, “01”. When a random number is generated during the monitored predetermined clock period and if there are many signals of an H level in the generated random number, the determination circuit 301 outputs a signal of an H level and a signal of an L level, that is, “10”. The latch PUF 300 generates individual-specific information using an RS latch circuit that outputs a fixed number and an RS latch circuit that outputs a random number. As illustrated in FIG. 3, the latch PUF 300 generates an ID [11:0] including a signal string “001011011100” using the outputs of the RS latch circuits 10-1 to 10-6.
The above technologies are described in International Publication Pamphlet No. WO 2011/117929, Japanese National Publication of International Patent Application No. 2003-526151, Japanese Laid-open Patent Publication No. 2004-127283, International Publication Pamphlet No. WO 2012/001796, and Japanese Laid-open Patent Publication No. 2013-131867.